// 2025/3/2
// https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
// 最长连续数组

class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            if(nums.size() == 0) return 0;
            sort(nums.begin(), nums.end());
            int ans = 0, count = 0, pre = nums[0] - 1;
            for(auto e : nums)
            {
                if(e == pre + 1) count++;
                else if(e != pre) count = 1;
    
                pre = e;
                ans = max(ans, count);
            }
            return ans;
        }
};

class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            int ans = 0;
            unordered_set<int> st(nums.begin(), nums.end()); // 把 nums 转成哈希集合
            for (int x : st) { // 遍历哈希集合
                if (st.contains(x - 1)) {
                    continue;
                }
                // x 是序列的起点
                int y = x + 1;
                while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
                    y++;
                }
                // 循环结束后，y-1 是最后一个在哈希集合中的数
                ans = max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
            }
            return ans;
        }
    };